package com.tingyuge.base.structrue.trie;


import java.util.TreeMap;

class MapSum {

    private Node root;


    private class Node {
        private int val;
        public TreeMap<Character, Node> next;

        public Node(int value) {
            this.val=  value;
            next = new TreeMap<>();
        }

        public Node() {
            this(0);
        }
    }
    /** Initialize your data structure here. */
    public MapSum() {
        this.root = new Node();
    }
    
    public void insert(String word, int val) {

        Node cur =root;
        for (int i = 0; i <word.length() ; i++) {
            char  c = word.charAt(i);

            if(cur.next.get(c) == null){
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
            
        }
        cur.val = val;

    }

    
    public int sum(String prefix) {

        Node cur = root;

        for (int i = 0; i <prefix.length() ; i++) {
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null){
                return 0;
            }
            cur = cur.next.get(c);


        }
        return sum(cur);

        
    }

    private int sum(Node node){
        if(node.next.size() ==0){return  node.val;}
        int res = node.val;
        for (char character : node.next.keySet()) {
            res += sum(node.next.get(character));

            
        }

        return  res;
    }
}